package Year22_Month05.day25;

import java.util.Arrays;

public class 快速排序3 {
    public static void main(String[] args) {
        int[] arr = {4,2,8,6,9,1,3,5,0,7};
        quickSort(arr,0,arr.length);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int left,int right){
        if(right - left > 1){
            int index = partion3(arr,left,right);
            quickSort(arr,left,index);
            quickSort(arr,index+1,right);
        }
    }

    public static int partion3(int[] arr,int left,int right){
        int index = right - 1;
        //然后是进行双指针版本需要的数据处理
        int key = arr[index];
        int cur = left;//这是后指针
        int pre = cur - 1;//这是前指针
        while(cur < right){
            //这是为了前后指针之间全部是大于key的值，然后有小于key的，就要往pre也就是前指针之前放
            if(arr[cur] < key && ++pre != cur){
                swap(arr,pre,cur);
            }
            cur++;
        }
        //最后判断一下pre往前走一位之后必定是大于key的值，此时交换pre和key的下标值
        if(++pre != index){
            swap(arr,index,pre);
        }
        return pre;
    }

    public static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
